﻿#define _CRT_SECURE_NO_WARNINGS 1

#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;

//1.暴力解法
//vector<int> twoSum(vector<int>& nums, int target)
//{
//    int n = nums.size();
//    for (int i = 0; i < n; i++)
//    {
//        for (int j = i + 1; j < n; j++)
//        {
//            if (nums[i] + nums[j] == target)
//                return { i,j };
//        }
//    }
//    return { -1,-1 };
//}

//2.借助哈希表
vector<int> twoSum(vector<int>& nums, int target) {
    unordered_map<int, int> hash;
    for (int i = 0; i < nums.size(); i++)
    {
        int tmp = nums[i];
        if (hash.count(target - tmp))
            return { hash[target - tmp],i };
        hash[tmp] = i;
    }
    return { -1,-1 };
}


vector<vector<string>> groupAnagrams(vector<string>& strs) {
    vector<vector<string>> ret;
    unordered_map<string, vector<string>> hash;

    for (auto& str : strs)
    {
        string tmp = str;
        sort(tmp.begin(), tmp.end());
        hash[tmp].push_back(str);
    }

    for (auto& e : hash)
    {
        ret.push_back(e.second);
    }
    return ret;
}

//行不通
//int longestConsecutive(vector<int>& nums) {
//    if (nums.size() == 0)
//        return 0;
//    sort(nums.begin(), nums.end());
//    int count = 1;
//    int ret = 0;
//    for (int i = 1; i < nums.size(); i++)
//    {
//        if (nums[i] - nums[i - 1] == 1)
//            count++;
//        else
//        {
//            ret = max(ret, count);
//            count = 1;
//        }
//    }
//    ret = max(ret, count);
//    return ret;
//}

int longestConsecutive(vector<int>& nums) {
    unordered_map<int, int> hash;
    //1. 先统计每个数字出现的次数
    for (auto& e : nums)
        hash[e]++;

    int ret = 0;
    for (auto& e : hash)
    {
        int x = e.first;
        //若nums[i-1]在哈希表中存在，则不能以i为起点，以i-1会更长
        if (hash.count(x - 1))
            continue;

        int y = x + 1;
        while (hash.count(y))
            y++;
        ret = max(ret, y - x);
    }
    return ret;
}

//
//void moveZeroes(vector<int>& nums) {
//    int n = nums.size();
//    if (n == 1)
//        return;
//    for (int i = 0; i < n; i++)
//    {
//        if (nums[i] == 0)
//        {
//            int j = i + 1;
//            while (j < n && nums[j] == 0)
//                j++;
//            if (j < n)
//                swap(nums[i], nums[j]);
//        }
//    }
//}

void moveZeroes(vector<int>& nums) {
    int left = 0, right = 0;
    while (right < nums.size())
    {
        if (nums[right] != 0)
        {
            swap(nums[left], nums[right]);
            left++; //left永远指向下一个非零数要放的位置
        }
        right++;
    }
}

